1. Field of the Invention
This invention relates generally to the field of steganography. More particularly, the present invention relates to the embedding and detection of watermark data in a data stream such as, for example, a video stream.
2. Description of the Related Art
The synergies between recently developed data compression techniques, high capacity storage media, the internet and other high bandwidth distribution channels have rendered digital media nearly ubiquitous. In view of these developments, technologies for the control of distribution, copying and identification of authorship and/or ownership of such media are gaining importance and relevance in the marketplace. In particular, the effective enforcement of copyrights in digital media is a complex problem, primarily due to the nature of the media itself. Indeed, unless preventative measures are taken, digital data is easily and perfectly reproducible, with no loss of fidelity.
So-called xe2x80x9cdigital watermarksxe2x80x9d have gained attention recently as one possible weapon in a content developer""s arsenal to combat piracy or unauthorized distribution or reproduction of digital media, such as video. In general, watermarks are a message, symbol or any distinctive marking that is transparently added to the video signal for the purpose of identifying whether the copy is an authorized one, the author of the video content, its distributor, owner or like information. The process of adding the distinctive message, symbol or marking to the digital media is generally referred to as the embedding process. Preferably, digital watermarks are embedded in the digital media (whether audio, still pictures or video) so as to render them invisible to the intended audience (such as, for example, moviegoers) and reliably detectable by appropriate detection systems. In general, visibility and detectability are directly related to one another: the more visible a watermark is, the more reliably it will be detected. Conversely, a well-concealed watermark may be difficult to reliably detect. An acceptable compromise between visibility and detectability, therefore, must typically be reached.
Several methods have been proposed to embed a watermark in a data stream. In the case of a video stream, for example, each video frame may be divided into a plurality of blocks of a given size. Each block, therefore, consists of a matrix of picture elements (hereafter, pixels), each having a number of characteristics associated therewith, such as luminance, chrominance etc. A transformation may be carried out for each pixel of each block. For example, a Discrete Cosine Transform (hereafter, DCT), a Discrete Fourier Transform (hereafter, DFT) or some other transformation may be carried out for each pixel of each block of each frame of the video stream. Such transformations produce a single cosine or sinusoid coefficient for each pixel, and give information related to the spectral content of the video stream. Once this information is obtained, a watermark or a portion thereof may be embedded in one or more blocks by evaluating and selectively modifying the coefficients of the transformed blocks of pixels. For example, a watermark or a portion thereof may be embedded as perturbations in the coefficients of single or a plurality of blocks. By selectively shifting the coefficients of matrices of DCT or DFT coefficients, for example, a watermark may be embedded with low visibility. This is possible, because the human visual and auditory systems do not readily distinguish between small variations in spectral content, making it possible for video information of a given frequency to mask watermark data of the same or an adjacent frequency.
Conventional methods relying on the transformation of each pixel of each block to determine their spectral content suffer from a number of disadvantages. Indeed, processing a large number of blocks, each of which may contain, for example, a matrix of 8xc3x978 pixels, or 16xc3x9716 pixels is a highly computationally intensive process. Such brute force processing of each pixel in each block of each frame is very demanding in terms of computational resources, time and cost. Such a scheme, to operate efficiently, requires costly dedicated hardware and substantial memory resources to keep pace with the high data rates of, for example, digital video. These problems are exacerbated on the detection side. Watermark detectors are typically deployed within consumer electronics, such as, for example, Digital Video (or Versatile) Disks (hereafter, DVD). Therefore, to reliably and accurately (low number of false positive watermark identifications) detect the watermarks using conventional schemes, each pixel of each block must be transformed into the frequency domain, and the obtained frequency coefficients evaluated for possible shifts indicative of a portion of a watermark. To gain widespread acceptance in the marketplace, however, the detection system must meet a number of criteria, including simplicity, reliability and low cost, so that it may be inexpensively incorporated in a variety of mass-market consumer electronics devices, such as DVD systems. These criteria appear to be at odds with a detection system requiring the transformation and testing of each pixel of each block of each frame of the entire data stream.
What are needed, therefore, are devices and methods for simply and reliably embedding and detecting watermarks or other similar hidden messages or symbols in digital data sets or data streams. Such a watermark embedding and detecting devices and methods should also be inexpensive to implement and to deploy in a wide array of devices, such as home consumer electronics devices, for example. What are also needed are devices and methods that reduce the number of operations required to invisibly embed and reliably detect watermarks or other similar hidden data in digital media. Preferably, such devices and methods would be compatible with a great variety of watermark embedding and detecting methods, including conventional frequency domain-centered embedding and detection schemes. Also, such watermark embedding and detecting devices and methods should decrease the time and number of computations necessary to process the data stream, as compared to conventional devices and methods.
It is, therefore, an object of the present invention to provide devices and methods for simply and reliably embedding and detecting watermarks or other similar hidden messages or symbols in digital data streams. It is another object of the present invention to provide watermark embedding and detecting devices and methods that are inexpensive to implement and to deploy in a wide array of devices. A further object is to provide devices and methods that reduce the number of operations required to invisibly embed and reliably detect watermarks or other similar hidden data in digital media. Another object is to provide such devices and methods that are compatible with a great variety of watermark embedding and detecting methods. A still further object is to provide devices and methods for embedding and detecting watermarks that decrease the time and number of computations necessary to process a given number of blocks, as compared to conventional devices and methods.
In accordance with the above-described objects and those that will be mentioned and will become apparent below, a watermark processing method, according to an embodiment of the present invention, comprises the steps of:
dividing a source data set into at least one block, each element of the source data set having at least one characteristic associated therewith;
testing each block to determine whether selected elements of each block exhibit at least a pre-selected degree of variation of at least one selected characteristic; and
processing a watermark only in those blocks that exhibit at least the pre-selected degree of variation of the selected characteristic.
According to other embodiments, the testing step may include a step of comparing the degree of variation of the selected characteristic with a threshold value. The testing step may include a step of subtracting a maximum value of the selected characteristic of the selected elements from a minimum value of the selected characteristic of the selected elements, the absolute value of the result being compared with the threshold value. The testing step may include a step of generating a sum of absolute values of differences of the selected characteristic of the selected elements, the sum of differences being compared with the threshold value. The source data set may include video and/or other types of data. The selected characteristic may include one or more characteristics selected from the group consisting of luminance, chrominance and RGB. The measure of variation may be determined in a pixel domain. The dividing step may divide the source data set into a plurality of equally sized blocks, each block including a matrix of data set elements having a size of at least 2xc3x971 elements. The data set elements may include picture elements (pixels). The processing step may include a step of embedding the watermark in each block of the data set that exhibits at least the pre-selected degree of variation of the at least one selected characteristic. The processing step may include a step of detecting the watermark only in those blocks of the data set that exhibit at least the pre-selected degree of variation of selected characteristic or characteristics. A step of de-emphasizing variations of the selected characteristic or characteristics along edges of each block relative to variations of the selected characteristic or characteristics within an interior of each block may be carried out. The de-emphasizing step may include a step of assigning a weighting coefficient to each element within each block, elements along edges of each block being assigned a lower coefficient than elements within an interior of each block.
The present invention may also be viewed as a device to embed a watermark in a data stream, the data stream including a plurality of data elements, each element having at least one characteristic associated therewith, comprising:
means for buffering and dividing the data stream into at least one block;
means for selecting blocks according to a texture criterion that measures a variation of a selected characteristic associated with each data element of the data stream,
means for embedding the watermark only in selected blocks.
According to further embodiments, the texture criterion may include at least one measure of variation of the characteristic or characteristics of selected elements of the data stream. The selecting means may evaluate the texture criterion in a spatial domain. The buffering and dividing means and the selecting means each may provide blocks to the embedding means, the embedding means being selectively disabled and enabled based upon an output of the selecting means. The buffering and dividing means may be connected to a first input of a logic device and to an input of the block selecting means, the block selecting means being connected to the embedding means whose output is connected to a second input of the logic device, the block selecting means controlling an operation of the logic device to cause the logic device to selectively output blocks with and without watermarks. The logic device may include a multiplexer. The selecting means may output a texture value to the embedding means, the embedding means modulating a strength of the watermark depending upon the magnitude of the texture value.
According to another embodiment, a device to detect a watermark in a data stream, the data stream including a plurality of data elements, each element having at least one characteristic associated therewith, according to the present invention comprises:
means for buffering and dividing the data stream into at least one block;
means for selecting blocks according to a texture criterion that measures a variation of a selected characteristic associated with each data element of the data stream,
means for detecting the watermark only in selected blocks.
According to still further embodiments, the texture criterion may include at least one measure of variation of the characteristic or characteristics of selected elements of the data stream. The selecting means may evaluate the texture criterion in a spatial domain. The detecting means may be selectively disabled and enabled depending upon an output of the selecting means. The texture criterion is preferably the same criterion that is used to select blocks in which to embed the watermark during a watermark embedding process. The selecting means may be the same selecting means that is used to select blocks in which to embed the watermark during an embedding process.
Another embodiment of the present invention is a watermark-based method of validating a data stream, comprising the steps of:
embedding a watermark only in portions of the data stream whose spectral energy exceeds a predetermined threshold according to a texture criterion, to create a watermarked data stream;
providing recording data stream playback devices with a selector configured to evaluate the texture criterion and to select only those portions of the data stream whose spectral energy exceeds the predetermined threshold; and
detecting the watermark only in the selected portions of the data stream.
According to other preferred embodiments, the data stream may include a video stream. A step of validating the data stream only when a watermark is detected in the data stream may also be carried out. A step of disallowing playback of the video stream when the data stream in not validated may also be carried out.
A still further embodiment of the present invention is a method of detecting a watermark in a watermarked data stream generated by a watermark embedding process, comprising the steps of:
dividing the data stream into a plurality of equally sized blocks;
selecting only those blocks likely to include a watermark using a same criterion as was used in the watermark embedding process;
accumulating the selected blocks in a spatial domain to reinforce the watermark, if present, relative to a relatively uncorrelated data stream.